package pro.softzhang.algo.lc0;

import pro.softzhang.algo.flag.theme.TMathArith;

/**
 *
 */
@TMathArith
public class LC29_DivideTwoIntegers {
    public static void main(String[] args) {
        int quotient = new LC29_DivideTwoIntegers().divide2(100,1);
        System.out.println(quotient);
    }

    /**
     * 方法一 暴力法，超出时间限制
     * @param a
     * @param b
     * @return
     */
    public int divide(int a, int b) {
        if(a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }

        int quotient = 1, aa = a > 0 ? -a : a, bb = b > 0 ? -b : b;
        for(; aa <= bb; aa = aa - bb){
            quotient++;
        }
        return ((a < 0 && b < 0) || (a > 0 && b > 0)) ? Math.abs(quotient) : quotient > 0 ? -quotient : quotient;
    }

    /**
     * 方法二 批量法，减少复杂度
     * @param a
     * @param b
     * @return
     */
    public int divide1(int a, int b) {
        if(a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }

        int quotient = 0, aa = a > 0 ? -a : a, bb = b > 0 ? -b : b;

        for (int mb = bb; aa >= mb; aa = aa - mb){
            mb += bb;
            quotient += 1;
        }

        return ((a < 0 && b < 0) || (a > 0 && b > 0)) ? Math.abs(quotient) : quotient > 0 ? -quotient : quotient;
    }

    /**
     * 书上的方式
     * @param dividend
     * @param divisor
     * @return
     */
    public int divide2(int dividend, int divisor) {
        if(dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        int flag = 2;
        if(dividend > 0) {
            flag--;
            dividend = -dividend;
        }

        if(divisor > 0) {
            flag--;
            divisor = -divisor;
        }

        int quotient = 0;
        while (dividend <= divisor) {
            int tmpDivisor = divisor, tmpQuotient = 1;
            // 通过
            while (tmpDivisor >= 0xc0000000 && dividend <= tmpDivisor * 2) {
                tmpDivisor *= 2;
                tmpQuotient *= 2;
            }
            dividend -= tmpDivisor;
            quotient += tmpQuotient;
        }
        return flag == 1 ? -quotient : quotient;
    }
}